#include <iostream>
#include <math.h>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <sstream>
#include <algorithm>
#include <assert.h>

using namespace std;

#define forn( i,n ) for ( int i=0; i<(int)(n); i++ )
// forn : for ( i en [0,n) )
#define fornin(i, desde, hasta) for ( int i=(desde); i<(int)(hasta); i++ )
// fornin : for ( i en [desde,hasta) )
#define decl(v, c) typeof(c) v = c
// decl : Declara la variable v igual que c
#define forall(i, c) for(decl(i, c.begin()); i!=c.end(); ++i)
// forall : foreach( i in c)
#define forallDist(i, j , c) for(decl(i, c.begin()); ((++i)--) != c.end(); i++) for(decl(j, ((++i)--)); j != c.end(); j++)
// forall : foreach( i,j in c) talque i != j

#define DBG(X) if (debug) cerr << #X << " = " << X << endl;
#define DBGendl() if(debug) cerr << endl;
#define DBGComment(String) if (debug) cerr << #String << endl;
#define DBGAssert(ExpresionBooleana) if (debug_assert && !(ExpresionBooleana)) cerr << #ExpresionBooleana << " ? " << false << endl;
#define DBGLista(A, tam) if(debug){ cerr << #A << " = " << endl << "\t\t["; forn(i, tam) cerr << A[i] << ", " ; cerr << "]" << endl; }
#define DBGListaPair(A, tam) if(debug){ cerr << #A << " = " << endl << "\t\t["; forn(i, tam) cerr << "(" <<A[i].first << ", "<< A[i].second <<"), "; cerr << "]" << endl; }
#define DBGMat(M, sizeX, sizeY) if(debug){ cerr << #M << " = " << endl; forn(x, (sizeX)) { forn(y, (sizeY)) cerr << "\t\t" << M[x][y]; cerr << endl;}}
#define DBGMatPair(M, sizeX, sizeY) if(debug){ cerr << #M << " = " << endl; forn(x, (sizeX)) { forn(y, (sizeY)) cerr << "\t[" << M[x][y].first << "," << M[x][y].second << "]"; cerr << endl;}}
#define DBGAssert(A) if(debug_assert) { assert((A)); }

typedef pair<int,int> intervalo;
bool debug          = false;
bool debug_assert   = false;

int base = 2;

float logEnBase(int n,int  base)
{
    return log10(n) / log10(base);
}

int potencia(int base,int exp)
{
    return (int)pow(base, exp);
}

int main()
{
    int cantidad_elementos = 0;
    int cantidad_busquedas = 0;

    while(cin >> cantidad_elementos && cantidad_elementos > 0)
    {
        cin >> cantidad_busquedas;

//        DBGendl();
//        DBG(cantidad_elementos);
//        DBG(cantidad_busquedas);
//        DBGAssert(cantidad_elementos > 0);
//        DBGAssert(cantidad_busquedas > 0);

        /** Creo el arreglo de los elementos agrupados apartir del original **/
        int elementos_agrupados[cantidad_elementos];    // Array de cantidades de elementos seguidas
        intervalo intervalos[cantidad_elementos];       // Array de mapeo de intervalo en cada grupo de lementos
        int posiciones_en_elem_agrupados[cantidad_elementos];   // Mapeo de la posicion original a la nueva.

        int elemento_anterior;
        int elemento_actual;
        int cantidad_actual;
        int principio_intervalo, final_intervalo; // Intervalo cerrado
        int posicion_actual_elementos_agrupados = 0;
        int posicion_en_elem_agrupados = 0;

        cin >> elemento_anterior;
        cantidad_actual = 1;
        principio_intervalo = 0;

        fornin(i, 1, cantidad_elementos)
        {
            cin >> elemento_actual;
            posiciones_en_elem_agrupados[posicion_en_elem_agrupados] = posicion_actual_elementos_agrupados;
            if(elemento_actual == elemento_anterior)
            {
                cantidad_actual++;
            }
            else
            {
                final_intervalo = posicion_en_elem_agrupados;
                elementos_agrupados[posicion_actual_elementos_agrupados] = cantidad_actual;
                intervalos[posicion_actual_elementos_agrupados] = intervalo(principio_intervalo, final_intervalo);
                cantidad_actual = 1;
                posicion_actual_elementos_agrupados++;
                principio_intervalo = posicion_en_elem_agrupados + 1;
            }
            elemento_anterior = elemento_actual;
            posicion_en_elem_agrupados++;
        }

        final_intervalo = posicion_en_elem_agrupados;
        posiciones_en_elem_agrupados[posicion_en_elem_agrupados] = posicion_actual_elementos_agrupados;
        elementos_agrupados[posicion_actual_elementos_agrupados] = cantidad_actual;
        intervalos[posicion_actual_elementos_agrupados] = intervalo(principio_intervalo, final_intervalo);
        posicion_actual_elementos_agrupados++;

        int cantidad_elementos_agrupados = posicion_actual_elementos_agrupados;

//        DBGendl();
//        DBGLista(elementos_agrupados, cantidad_elementos_agrupados);
//        DBGLista(posiciones_en_elem_agrupados, cantidad_elementos);
//        DBGListaPair(intervalos, cantidad_elementos_agrupados);

        int log_cant_elem = max((int)(1), (int)ceil(logEnBase(cantidad_elementos_agrupados, base)));

        int   maximos[cantidad_elementos][log_cant_elem];

        forn(i, cantidad_elementos_agrupados) forn(j, log_cant_elem)
        {
            maximos[i][j] = 0;
            if(j == 0)
                maximos[i][j] = elementos_agrupados[i];
        }


        int tam_intervalo =  1;
        fornin(potencia, 1, log_cant_elem)
        {
            int tam_intervalo_anterior  = tam_intervalo;
            tam_intervalo *= base;
            int potencia_anterior       = potencia -1;

            forn(pos, cantidad_elementos_agrupados)
            {

                int principio_anterior_1    = pos;
                int final_anterior_1        = principio_anterior_1 + tam_intervalo_anterior - 1;
                int principio_anterior_2    = final_anterior_1 + 1;
                int final_anterior_2        = principio_anterior_2 + tam_intervalo_anterior - 1;

//                DBG(tam_intervalo);
//                DBG(tam_intervalo_anterior);
//                DBG(principio_anterior_1);
//                DBG(final_anterior_1);
//                DBG(principio_anterior_2);
//                DBG(final_anterior_2);

                int el_maximo = 0;
                if(final_anterior_2 < cantidad_elementos_agrupados)
                {
                    el_maximo = max(   maximos[principio_anterior_1][potencia_anterior],
                                       maximos[principio_anterior_2][potencia_anterior]);
                }
                maximos[pos][potencia] = el_maximo;
            }
        }

        DBGMat(maximos, cantidad_elementos_agrupados, log_cant_elem);

        forn(busqueda_k, cantidad_busquedas)
        {
            int desde, hasta, diferencia;
            cin >> desde >> hasta;

            desde--;
            hasta--;
//            DBG(desde);
//            DBG(hasta);

            int max_principio = 0;
            int posicion_en_elem_agrup_desde = posiciones_en_elem_agrupados[desde];
            if(intervalos[posicion_en_elem_agrup_desde].first != desde)
            {
                max_principio = min(intervalos[posicion_en_elem_agrup_desde].second, hasta) - desde + 1;
                desde = intervalos[posicion_en_elem_agrup_desde].second + 1;
            }

            int max_final = 0;
            int posicion_en_elem_agrup_hasta = posiciones_en_elem_agrupados[hasta];
            if(intervalos[posicion_en_elem_agrup_hasta].second != hasta)
            {
                max_final = hasta - max(intervalos[posicion_en_elem_agrup_hasta].first, desde) + 1;
                hasta = intervalos[posicion_en_elem_agrup_hasta].first - 1;
            }


            int cantidad_maxima = 1;

            diferencia = hasta - desde + 1 ;
            if(diferencia > 0)
            {
//                DBG(desde);
//                DBG(hasta);
                desde = posiciones_en_elem_agrupados[desde];
                hasta = posiciones_en_elem_agrupados[hasta];
                diferencia = hasta - desde + 1 ;

                int potencia_anterior = max(int(0), (int)floor(logEnBase(diferencia, base)));
                int tam_intervalo = max(int(0), potencia(base, potencia_anterior));
                int desplazamiento = diferencia - tam_intervalo;
                int desde_2 = desde + desplazamiento;

//                DBG(potencia_anterior);
//                DBG(tam_intervalo);
//                DBG(desplazamiento);
//                DBG(desde_2);

                cantidad_maxima = max(maximos[desde][potencia_anterior], maximos[desde_2][potencia_anterior]);
            }
//            DBG(desde);
//            DBG(hasta);
//            DBG(diferencia);
//            DBG(cantidad_maxima);
//            DBG(max_principio);
//            DBG(max_final);
//            DBGendl();
//            DBGendl();

            cantidad_maxima = max(cantidad_maxima, max_principio);
            cantidad_maxima = max(cantidad_maxima, max_final);

            cout << cantidad_maxima << endl;
//            DBGendl();
//            DBGendl();
        }
    }
//
//    DBGComment("Hello world!");
//    DBGendl();
    return 0;
}
